/**
 * @file review.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-03-02
 *
 * @copyright Copyright (c) 2022
 *
 */

// 链表的移除元素、反转
// 链表的交点，环

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
  public:
    // 203. 移除元素
    ListNode *removeElements(ListNode *head, int val)
    {
        // 递归出口
        if (head == nullptr) {
            return nullptr;
        }
        head->next = removeElements(head->next, val);
        if (head->val == val) {
            return head->next;
        }
        return head;
    }
    ListNode *removeElements2(ListNode *head, int val)
    {
        ListNode *dummy = new ListNode(0, head);
        ListNode *pre = dummy, *cur = head;
        while (cur) {
            if (cur->val == val) {
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
    // 206. 反转链表
    ListNode *reverseList(ListNode *head)
    {
        // 递归出口：空节点或一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    ListNode *reverseList2(ListNode *head)
    {
        ListNode *pre = nullptr;
        while (head) {
            ListNode *post = head->next;
            head->next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }
    // 24. 两两交换链表节点
    ListNode *swapPairs(ListNode *head)
    {
        // 递归出口：空节点或一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *post = head->next;
        head->next = swapPairs(head->next->next);
        post->next = head;
        return post;
    }
    ListNode *swapPairs2(ListNode *head)
    {
        ListNode *dummy = new ListNode(0, head);
        ListNode *cur = dummy;
        while (cur->next && cur->next->next) {
            ListNode *one = cur->next;
            ListNode *three = cur->next->next->next;
            cur->next = one->next; // dummy->2
            one->next->next = one; // 2->1
            one->next = three;     // 1->3
            cur = cur->next->next;
        }
        return dummy->next;
    }
    // 19. 删除倒数第N个节点
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *dummy = new ListNode(0, head);
        ListNode *fast = dummy, *slow = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        // fast指向最后一个节点，slow指向要删除的前驱节点
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }
    // 160. 相交链表找交点
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 数学题：双指针一起跑，跑的路程都是m+n
        // 若有交点一定会相遇
        // 若无交点，都会等于nullptr退出循环
        ListNode *curA = headA, *curB = headB;
        while (curA != curB) {
            curA = curA ? curA->next : headB;
            curB = curB ? curB->next : headA;
        }
        return curA;
    }
    // 141. 判断链表是否有环
    bool hasCycle(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) { // 相遇则有环
                return true;
            }
        }
        return false;
    }
    // 142. 寻找环形链表入口
    ListNode *detectCycle(ListNode *head)
    {
        if (!head || !head->next) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        bool hasCycle = false;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return nullptr;
        }
        // 有环
        while (head != slow) {
            head = head->next;
            slow = slow->next;
        }
        return slow;
    }
    int findDuplicate(vector<int> &nums)
    {
        // 方法二：环形链表思想 O(N) + O(1)
        // 而且是必有环的情况
        // idx->nums[idx] 把数组的值理解成next指针
        int slow = 0, fast = 0;
        while (1) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (slow == fast) {
                break;
            }
        }
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};